//
//  MergeSort.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/7.
//  Copyright © 2017年 aron. All rights reserved.
//

#include "MergeSort.h"
#include "stdlib.h"

void MSort(ElementType arr[], ElementType tmpArr[], int left, int right) {
    int Center;
    if (left < right) {
        Center = (left + right) / 2;
        
        MSort(arr, tmpArr, left, Center);
        MSort(arr, tmpArr, Center+1, right);
        // [left, center]、[center+1, right] 这两部分是排好序的了，合并这两部分
        Merge(arr, tmpArr, left, Center+1, right);
    }
}

void MergeSort(ElementType arr[], int count) {
    ElementType *tmpArr = malloc(count * sizeof(ElementType));
    MSort(arr, tmpArr, 0, count-1);
}

void Merge(ElementType arr[], ElementType tmpArr[], int lPos, int rPos, int rightEnd) {
    int i, leftEnd, tmpPos, count;
    leftEnd = rPos - 1;
    tmpPos = lPos;
    count = rightEnd - lPos + 1;
    // 比较元素复制到临时数组中,！！注意需要使用<=符号
    while (lPos <= leftEnd && rPos <= rightEnd) {
        if (arr[lPos] < arr[rPos]) {
            tmpArr[tmpPos++] = arr[lPos++];
        } else {
            tmpArr[tmpPos++] = arr[rPos++];
        }
    }
    // 拷贝剩余的元素到临时数组中！！注意需要使用<=符号
    while (lPos <= leftEnd) {
        tmpArr[tmpPos++] = arr[lPos++];
    }
    while (rPos <= rightEnd) {
        tmpArr[tmpPos++] = arr[rPos++];
    }
    
    // 把排序的元素复制到原来的数组中
    for (i = 0; i<count; i++, rightEnd--) {
        arr[rightEnd] = tmpArr[rightEnd];
    }
}
